Teach __tree how to handle map's __value_type This patch is fairly large and contains a number of changes. The changes all work towards allowing __tree to properly handle __value_type esspecially when inserting into the __tree. I chose not to break this change into smaller patches because it wouldn't be possible to write meaningful standard-compliant tests for each patch. It is very similar to r260513 "[libcxx] Teach __hash_table how to handle unordered_map's __hash_value_type". Changes in <map> * Remove __value_type's constructors because it should never be constructed directly. * Make map::emplace and multimap::emplace forward to __tree and remove the old definitions * Remove "__construct_node" map and multimap member functions. Almost all of the construction is done within __tree. * Fix map's move constructor to access "__value_type.__nc" directly and pass this object to __tree::insert. Changes in <__tree> * Add traits to detect, handle, and unwrap, map's "__value_type". * Convert methods taking "value_type" to take "__container_value_type" instead. Previously these methods caused unwanted implicit conversions from "std::pair<Key, Value>" to "__value_type<Key, Value>". * Delete __tree_node and __tree_node_base's constructors and assignment operators. The node types should never be constructed because the "__value_" member of __tree_node must be constructed directly by the allocator. * Make the __tree_node_destructor class and "__construct_node" methods unwrap "__node_value_type" into "__container_value_type" before invoking the allocator. The user's allocator can only be used to construct and destroy the container's value_type. Passing it map's "__value_type" was incorrect. * Cleanup the "__insert" and "__emplace" methods. Have __insert forward to an __emplace function wherever possible to reduce code duplication. __insert_unique(value_type const&) and __insert_unique(value_type&&) forward to __emplace_unique_key_args. These functions will not allocate a new node if the value is already in the tree. * Change the __find* functions to take the "key_type" directly instead of passing in "value_type" and unwrapping the key later. This change allows the find functions to be used without having to construct a "value_type" first. This allows for a number of optimizations. * Teach __move_assign and __assign_multi methods to unwrap map's __value_type. git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@264986 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/map b/include/map index c946ca0..a459146 100644 --- a/include/map +++ b/include/map
@@ -626,33 +626,29 @@ value_type __cc; __nc_value_type __nc; - template <class ..._Args> - _LIBCPP_INLINE_VISIBILITY - __value_type(_Args&& ...__args) - : __cc(std::forward<_Args>(__args)...) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(const __value_type& __v) - : __cc(__v.__cc) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(__value_type& __v) - : __cc(__v.__cc) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(__value_type&& __v) - : __nc(std::move(__v.__nc)) {} - _LIBCPP_INLINE_VISIBILITY __value_type& operator=(const __value_type& __v) {__nc = __v.__cc; return *this;} _LIBCPP_INLINE_VISIBILITY __value_type& operator=(__value_type&& __v) - {__nc = std::move(__v.__nc); return *this;} + {__nc = _VSTD::move(__v.__nc); return *this;} + template <class _ValueTp, + class = typename enable_if< + __is_same_uncvref<_ValueTp, value_type>::value + >::type + > _LIBCPP_INLINE_VISIBILITY - ~__value_type() {__cc.~value_type();} + __value_type& operator=(_ValueTp&& __v) { + __nc = _VSTD::forward<_ValueTp>(__v); return *this; + } + +private: + __value_type() _LIBCPP_EQUAL_DELETE; + ~__value_type() _LIBCPP_EQUAL_DELETE; + __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE; + __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE; }; #else @@ -666,18 +662,11 @@ value_type __cc; - _LIBCPP_INLINE_VISIBILITY - __value_type() {} - - template <class _A0> - _LIBCPP_INLINE_VISIBILITY - __value_type(const _A0& __a0) - : __cc(__a0) {} - - template <class _A0, class _A1> - _LIBCPP_INLINE_VISIBILITY - __value_type(const _A0& __a0, const _A1& __a1) - : __cc(__a0, __a1) {} +private: + __value_type(); + __value_type(__value_type const&); + __value_type& operator=(__value_type const&); + ~__value_type(); }; #endif @@ -1051,18 +1040,18 @@ _LIBCPP_INLINE_VISIBILITY value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS +#ifndef _LIBCPP_CXX03_LANG + template <class ..._Args> + _LIBCPP_INLINE_VISIBILITY + pair<iterator, bool> emplace(_Args&& ...__args) { + return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...); + } template <class ..._Args> - pair<iterator, bool> - emplace(_Args&& ...__args); - - template <class ..._Args> - iterator - emplace_hint(const_iterator __p, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS + _LIBCPP_INLINE_VISIBILITY + iterator emplace_hint(const_iterator __p, _Args&& ...__args) { + return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...); + } template <class _Pp, class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> @@ -1076,7 +1065,7 @@ iterator insert(const_iterator __pos, _Pp&& __p) {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> @@ -1088,14 +1077,15 @@ {return __tree_.__insert_unique(__p.__i_, __v);} #if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) + // TODO(EricWF): These functions are C++17 only but they should probably + // be exposed in C++11. _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> - insert( value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward<value_type>(__v));} + insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY - iterator - insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_unique(__p.__i_, _VSTD::forward<value_type>(__v));} + iterator insert(const_iterator __p, value_type&& __v) + {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));} #endif template <class _InputIterator> @@ -1331,16 +1321,10 @@ typedef __map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(); - template <class _A0> - __node_holder __construct_node(_A0&& __a0); +#ifndef _LIBCPP_CXX03_LANG __node_holder __construct_node_with_key(key_type&& __k); -#ifndef _LIBCPP_HAS_NO_VARIADICS - template <class _A0, class _A1, class ..._Args> - __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS #endif + __node_holder __construct_node_with_key(const key_type& __k); __node_base_pointer const& @@ -1401,7 +1385,7 @@ return __parent->__left_; } -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +#ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) @@ -1412,35 +1396,10 @@ const_iterator __e = cend(); while (!__m.empty()) __tree_.__insert_unique(__e.__i_, - _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); + _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc)); } } -template <class _Key, class _Tp, class _Compare, class _Allocator> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node() -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class _A0> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} template <class _Key, class _Tp, class _Compare, class _Allocator> typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder @@ -1455,26 +1414,7 @@ return __h; } -#ifndef _LIBCPP_HAS_NO_VARIADICS - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class _A0, class _A1, class ..._Args> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), - _VSTD::forward<_Args>(__args)...); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -#endif // _LIBCPP_HAS_NO_VARIADICS - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // !_LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder @@ -1551,34 +1491,6 @@ return static_cast<__node_pointer>(__child)->__value_.__cc.second; } -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool> -map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get()); - if (__r.second) - __h.release(); - return __r; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -typename map<_Key, _Tp, _Compare, _Allocator>::iterator -map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, - _Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get()); - if (__r.__i_.__ptr_ == __h.get()) - __h.release(); - return __r; -} - -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) template <class _Key, class _Tp, class _Compare, class _Allocator> inline _LIBCPP_INLINE_VISIBILITY @@ -1876,18 +1788,19 @@ value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS +#ifndef _LIBCPP_CXX03_LANG template <class ..._Args> - iterator - emplace(_Args&& ...__args); + _LIBCPP_INLINE_VISIBILITY + iterator emplace(_Args&& ...__args) { + return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); + } template <class ..._Args> - iterator - emplace_hint(const_iterator __p, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS + _LIBCPP_INLINE_VISIBILITY + iterator emplace_hint(const_iterator __p, _Args&& ...__args) { + return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); + } template <class _Pp, class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> @@ -1901,7 +1814,7 @@ iterator insert(const_iterator __pos, _Pp&& __p) {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} @@ -1911,12 +1824,15 @@ {return __tree_.__insert_multi(__p.__i_, __v);} #if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) + // TODO(EricWF): These functions are C++17 only but they should probably + // be exposed in C++11. _LIBCPP_INLINE_VISIBILITY - iterator insert( value_type&& __v) {return __tree_.__insert_multi(_VSTD::forward<value_type>(__v));} + iterator insert(value_type&& __v) + {return __tree_.__insert_multi(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_multi(__p.__i_, _VSTD::forward<value_type>(__v));} + {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} #endif template <class _InputIterator> @@ -2035,21 +1951,9 @@ typedef __map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(); - template <class _A0> - __node_holder - __construct_node(_A0&& __a0); -#ifndef _LIBCPP_HAS_NO_VARIADICS - template <class _A0, class _A1, class ..._Args> - __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES }; -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - +#ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) : __tree_(_VSTD::move(__m.__tree_), __a) @@ -2059,82 +1963,10 @@ const_iterator __e = cend(); while (!__m.empty()) __tree_.__insert_multi(__e.__i_, - _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); + _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc)); } } - -template <class _Key, class _Tp, class _Compare, class _Allocator> -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node() -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class _A0> -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -#ifndef _LIBCPP_HAS_NO_VARIADICS - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class _A0, class _A1, class ..._Args> -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), - _VSTD::forward<_Args>(__args)...); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator -multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_multi(__h.get()); - __h.release(); - return __r; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator -multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, - _Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get()); - __h.release(); - return __r; -} - -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) +#endif template <class _Key, class _Tp, class _Compare, class _Allocator> inline _LIBCPP_INLINE_VISIBILITY 